/* 99. 恢复二叉搜索树 */
function TreeNode(val, left, right) {
	this.val = val == null ? 0 : val
	this.left = left == null ? null : left
	this.right = right == null ? null : right
}
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var recoverTree = function (root) {
	let prev = new TreeNode(-Infinity)
	let err1,
		err2 = null
	const inOrder = (root) => {
		if (!root) return
		inOrder(root.left)
		if (prev.val >= root.val && err1 == null) {
			// 当前是第一对错误
			err1 = prev
		}
		if (prev.val >= root.val && err1 != null) {
			// 记录第二个错误点
			err2 = prev
		}
		prev = root
		inOrder(root.right)
	}
	inOrder(root)
	const temp = err1.val
	err1.val = err2.val
	err2.val = temp
}
/* 显示中序 */
var recoverTree = function (root) {
	const nums = []
	const inOrder = (root, nums) => {
		if (root == null) return
		inOrder(root.left, nums)
		nums.push(root.val)
		inOrder(root.right, nums)
	}
	const findTwoSwapped = (nums) => {
		const n = nums.length
		let index1 = -1,
			index2 = -1
		for (let i = 0; i < n - 1; i++) {
			if (nums[i + 1] < nums[i]) {
				index2 = i + 1
				if (index1 === -1) {
					index1 = i
				} else break
			}
		}
		let x = nums[index1],
			y = nums[index2]

		return [x, y]
	}
	const recover = (r, count, x, y) => {
		if (r === null) return
		if (r.val === x || r.val === y) {
			r.val = r.val === x ? y : x
			if (--count === 0) return
		}
		recover(r.left, count, x, y)
		recover(r.right, count, x, y)
	}
	inOrder(root, nums)
	const [first, second] = findTwoSwapped(nums)
	recover(root, 2, first, second)
}
/* 隐式中序遍历 */
var recoverTree = function (root) {
	const stack = []
	let x = null,
		y = null,
		prev = null

	while (stack.length || root !== null) {
		while (root) {
			stack.push(root)
			root = root.left
		}
		root = stack.pop()
		if (prev !== null && root.val < prev.val) {
			y = root
			if (x === null) {
				x = prev
			} else break
		}
		prev = root
		root = root.right
	}
	swap(x, y)
}
/* Morris 中序遍历  */
var recoverTree = function (root) {
	let x = null,
		y = null,
		prev = null,
		predecessor = null //前驱点

	while (root) {
		if (root.left) {
			// predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止
			predecessor = root.left
			while (predecessor.right && predecessor.right !== root) {
				predecessor = predecessor.right
			}
			// 让predecessor 的右指针指向根节点，继续遍历左子节点
			if (!predecessor.right) {
				predecessor.right = root
				root = root.left
			} else {
				/* 说明左子树已经访问完了，我们需要断开链接 */
				if (prev && root.val < prev.val) {
					y = root
					if (x == null) {
						x = prev
					}
				}
				prev = root
				predecessor.right = null
				root = root.right
			}
		} else {
			if (prev && root.val < prev.val) {
				y = root
				if (x == null) {
					x = prev
				}
			}

			prev = root
			root = root.right
		}
	}
	swap(x, y)
}
const swap = (x, y) => {
	const temp = x.val
	x.val = y.val
	y.val = temp
}
